package com.xzz.tree;

/**
 * @author: hhz
 * @create: 2021-12-17 11:25
 * l 116
 * 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 * <p>
 * 初始状态下，所有next 指针都被设置为 NULL。
 **/
public class Connect {

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node1.left = node2;
        node1.right = node3;
        preTraverse(node1);
//        Node connect = connect(node1);
        Node connect = connect2(node1);
        System.out.println();
        preTraverse(connect);
    }

    public static Node connect(Node root) {
        if (null != root) {
            connectTo(root.left, root.right);
        }
        return root;
    }
    public static Node connect2(Node root) {
        if (null != root && root.left!=null) {
            root.left.next = root.right;
            if(root.next!=null && root.next.left!=null){
                root.right.next = root.next.left;
            }
            connect2(root.left);
            connect2(root.right);

        }
        return root;
    }

    public static void connectTo(Node node1, Node node2) {
        if (null != node1 && null != node2) {
            node1.next = node2;
            connectTo(node1.left,node1.right);
            connectTo(node2.left,node2.right);
            connectTo(node1.right,node2.left);
        }
    }

    public static void preTraverse(Node node) {
        if (node != null) {
            System.out.print(node.val + " ");
            if (node.next != null) {
                System.out.print("# ");
            }
            preTraverse(node.left);
            preTraverse(node.right);
        }
    }
}
